1447D - Catching Cheaters - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define all(v)				((v).begin()), ((v).end())
#define rall(v)				((v).rbegin()), ((v).rend())
#define oo 1e18+5
#define MOD ll(1e9+7)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
# define M_PI  3.14159265358979323846
#define int long long
typedef int ll;
typedef vector<ll> vi;
typedef vector<vi> vii;
typedef pair<ll,ll> pi;
typedef pair<ll,pi> pii;
typedef vector<pi> vip;
typedef vector<vip> viip;
typedef map<ll,ll> mapi;;
typedef tree< pi, null_type, less<pi>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int N=2e5+5;
///// Agamista


string x,y;
ll n,m;
ll dp[5005][5005];
ll LCS(ll inx1 ,ll inx2) {
    if (inx1 >= n || inx2 >= m)return 0;
    if (dp[inx1][inx2] != -1)return dp[inx1][inx2];
    ll opt1 = 0, opt2 = 0, opt3 = 0, opt4 = 0;
    if (x[inx1] == y[inx2]) {
        opt3 = LCS(inx1 + 1, inx2 + 1) + 2;
    } else {
        opt1 = LCS(inx1 + 1, inx2) - 1;
        opt2 = LCS(inx1, inx2 + 1) - 1;
        opt4 = LCS(oo, oo);
    }
    dp[inx1][inx2] = max3(opt1, opt2, max(opt3, opt4));
    return max3(opt1, opt2, opt3);
}

void solve() {
    cin >> n >> m;
    cin >> x >> y;
    memset(dp, -1, sizeof dp);
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            ans = max(ans, LCS(i, j));
        }
    }
    cout << ans << endl;
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}